package com.learn.hd.swap;

import java.util.Arrays;

/**
 * @author zhanghaidong
 * @version v1.0
 * @description 交换排序-----快速排序
 * @date 2019/7/15
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] array = new int[]{ 4, 6, 1, 9, 12, 45, 19, 100, 7};


        quickSort(array, 0, array.length-1);

        System.out.println(Arrays.toString(array));

    }

    public static void quickSort(int[] array, int startIndex, int endIndex) {

        if (startIndex >= endIndex) {
            return;
        }
        int index = division(array, startIndex, endIndex);
        quickSort(array, startIndex, index-1);
        quickSort(array, index+1, endIndex);
    }

    /**
     * 挖坑法 分治
     * @param array
     * @param startIndex
     * @param endIndex
     * @return
     */
    public static int division(int[] array, int startIndex, int endIndex) {

        int base = array[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left < right) {

            while (left < right && array[right] >= base) {
                right--;
            }
            if (left < right) {
                array[left] = array[right];
                left++;
            }

            while (left < right && array[left] <= base) {
                left++;
            }
            if (left < right) {
                array[right] = array[left];
                right--;
            }
        }

        array[left] = base;
        return left;
    }
}
